from data_types import Point, Segment, Triangle
from itertools import combinations

def point_in_one_of_segments(convex_hull_points, point):
    for p1, p2 in combinations(convex_hull_points, 2):
        if point_on_segment(Segment(p1, p2), point):
            return True
    return False

def point_in_one_of_triangles(convex_hull_points, point):
    for p1, p2, p3 in combinations(convex_hull_points, 3):
        if point_in_triangle(Triangle(p1, p2, p3), point):
            return True
    return False

def naive_closed_convex(points):
    convex_hull_points = []
    for point in points:
        point_on_segment = point_in_one_line_of(convex_hull_points, point)
        if point_on_segment:
            continue
        
        point_in_triangle = point_in_one_of_triangles(convex_hull_points, point)
        if point_on_segment:
            continue
        convex_hull_points.append(point)
        
    return set(convex_hull_points)

def all_points_in_same_sphere(segment, points):
    last_p = None
    segment_points = (segment.p1, segment.p2)
    for p3 in points:
        if p3 in segment_points:
            continue
        if last_p is not None:
            different_sphere = points_in_different_sides_of_segment(segment, p3, last_p) in (TwoPointSide.DIFFERENT_SIDES, TwoPointSide.ON_LINE,)
            if different_sphere:
                return False
        last_p = p3
    return True

def naive_convex_hull2(points):
    convex_hull_points = []
    for p1, p2 in combinations(points, 2):
        segment = Segment(p1, p2)
        if all_points_in_same_sphere(segment, points):
            convex_hull_points.append(p1)
            convex_hull_points.append(p2)

    return set(convex_hull_points)

def naive_convex_hull3(points):
    convex_hull_points = set()

    i = 0
    first_point = None
    for (_, p1), (j, p2) in combinations(enumerate(points), 2):
        segment = Segment(p1, p2)
        if all_points_in_same_sphere(segment, points):
            first_point = p1
            convex_hull_points.add(p2)
            i = j
            break
        
    while points[i] != first_point:
        p1 = points[i]
        for j, p2 in enumerate(points):
            
            segment = Segment(p1, p2)
            if all_points_in_same_sphere(segment, points):
                convex_hull_points.add(p2)
                i = j
                break

    convex_hull_points.add(first_point)

    return convex_hull_points

def find_chain(points):
    s, points = points[:2], points[2:]
    for p in points:
        while len(s) >= 2 and turn_direction(Segment(s[-2], s[-1]), Segment(s[-1], p)) == TurnDirection.RIGHT:
            s.pop()
        s.append(p)

    return s

def grahm_convex_hull1(points):
    points = sorted(points, cmp = lambda p1, p2: p1.x < p2.x or p1.x == p2.x and p1.y > p2.y)
    inverted_points = points[::-1]
    
    bottom_chain = find_chain(points)
    top_chain = find_chain(inverted_points)
    
    return bottom_chain[:-1] + top_chain[:-1] # remove last point (will be added by the second chain)
    


def polaric_order(p, p1, p2):
    direction = turn_direction(Segment(p, p1), Segment(p1, p2))
    if direction == TurnDirection.SAME_LINE:
        return __cmp__(p2.y, p1.y)
    elif direction == TurnDirection.LEFT:
        return 1
    else:
        return -1
    
def grahm_convex_hull2(points):
    i, min_y_p = min(enumerate(points), key = lambda p: p[1].y)
    points = points[:i] + points[i + 1:]

    polaric_sorted = sorted(points, cmp = partial(polaric_order, p = min_y_p))
    top_chain = find_chain(polaric_sorted)
    return min_y_p + top_chain

class LeveledConvexHull(object):
    def __init__(self, points):
        super(LeveledConvexHull, self).__init__()
        self.levels = [points]
        self.update_levels()

    def update_levels(self):
        self.levels = [self.levels[0]]
        while len(self.levels[-1]) > 3:
            self.levels.append(self.levels[-1][::2])

    def is_point_included(self, point):
        point_index = 0
        # we have logn levels
        for level in islice(self.levels, step = -1):
            triangle = Triangle(
                level[point_index], 
                level[point_index + 1], 
                level[point_index + 2], 
            )
            in_phase1, in_phase2, in_phase3 = point_in_triangle_phase(
                triangle, point)
            # if it is in the triangle then it is already inside 
            # the closed convex
            if in_phase1 and in_phase2 and in_phase3:
                return None
            # if it is not in the triangle, make sure its
            # not zavit kodkodit (angle parietal???). if it is zavit kodkodit, 
            # then it must be outside the closed convex. i dont handle this 
            # case specifically (although it can improve the performance) 
            # because i want to find the index of the lower level
            if in_phase1 and not in_phase2 and not in_phase3:
                point_index = 2 * point_index
            elif in_phase1 and not in_phase2 and not in_phase3:
                point_index = 2 * (point_index + 1)
            elif in_phase1 and not in_phase2 and not in_phase3:
                point_index = 2 * (point_index + 2)

        return point_index

    def update_point(self, point):
        point_index = self.is_point_included(point)
        if point_index is None:
            return

        # start updating the structure. this is log(n) work because 
        # we have logn levels

        # first, find where we should put the new point
        level = self.levels[0]
        first_index = (point_index - 1) % len(level)
        while points_in_different_sides_of_line(
                Line(level[first_index], level[first_index + 1]), 
                level[point_index], point):
            first_index = (first_index - 1) % len(level)
        last_index = (point_index - 1) % len(level)
        while points_in_different_sides_of_line(
                Line(level[last_index], level[last_index - 1]), 
                level[point_index], point):
            last_index = (first_index + 1) % len(level)

        # Then, update for the rest of the levels - 
        for level in self.levels:
            # remove all the points between the found points which make it
            # a closed convex
            del level[first_index:last_index]
            # update the shape to include the added (outside) point
            level[first_index] = point

            first_index = first_index / 2
            last_index = last_index / 2
            
    def next_point(self, point):
        point_index = 1
        for level in islice(self.levels, step = -1):
            pts = level[point_index - 1], level[point_index], level[point_index + 1]
            segments = [Segment(point, p) for p in pts] # this is O(1), cuz we have here 3 points only
            min_angle_point_index = min(enumerate(segments), cmpfunc = compare_segment_angles)[0]
            
            point_index_offset = min_angle_point_index - 1
            interesting_point_index = point_index + point_index_offset
            point_index = 2 * interesting_point_index
        return self.levels[0][point_index]
            
def compare_segment_angles((_, segment1), (_, segment2)):
    direction = same_direction(segment1, segment2)
    if direction == SameDirection.CounterClockwise: return 1
    elif direction == SameDirection.Clockwise: return -1
    else: return 0
    

def jarviss_convex_hull_lch(points):
    # o(nlogn)
    lch = LeveledConvexHull(points)
    
    convex_hull_points = []
    
    # o(n)
    p = min_y_p = min(enumerate(points), key = lambda p: p[1].y)[1]
    convex_hull_points.append(p)
    next_ch_point = lch.next_point(p)
    # n times
    while next_ch_point != min_y_p:
        # logn each one
        convex_hull_points.append(next_ch_point)
        next_ch_point = lch.next_point(p)
        
    return convex_hull_points
    
def next_jarviss_point(points, point):
    # kitson query
    segments = [Segment(point, p) for p in points] # this is O(1), cuz we have here 3 points only
    min_index = min(enumerate(segments), cmpfunc = compare_segment_angles)[0]
    return points[min_index]

    
def jarviss_convex_hull(points):
    # o(nlogn)
    convex_hull_points = []
    
    # o(n)
    p = min_y_p = min(enumerate(points), key = lambda p: p[1].y)[1]
    convex_hull_points.append(p)
    next_ch_point = next_jarviss_point(points, p)
    # n times
    while next_ch_point != min_y_p:
        # logn each one
        convex_hull_points.append(next_ch_point)
        next_ch_point = next_jarviss_point(points, p)
        
    return convex_hull_points
    
def chan_convex_hull_h_known(points, h):
    chan_groups = grouper(points, h)
    # notice k = len(chan_groups)
    jarviss_convex_hulls = [jarviss_convex_hull(g) for g in chan_groups]
    
    
    lchs = [LeveledConvexHull(g) for g in chan_groups]
    
    convex_hull_points = []
    
    # o(n)
    p = min_y_p = min(enumerate(points), key = lambda p: p[1].y)[1]
    convex_hull_points.append(p)
    next_ch_point = next_jarviss_point([lch.next_point(p) for lch in lchs], p)
    # n times
    for i in xrange(h):
        # logn each one
        convex_hull_points.append(next_ch_point)
        next_ch_point = next_jarviss_point([lch.next_point(p) for lch in lchs], p)
        if next_ch_point == min_y_p: break
        
    if next_ch_point != min_y_p: return None
    
    return convex_hull_points
    
def chan_convex_hull(points):
    h = 2
    convex_hull_points = chan_convex_hull_h_known(points, h)
    while convex_hull_points is None:
        h <<= 1
        convex_hull_points = chan_convex_hull_h_known(points, h)
        
    return convex_hull_points